PRACTICE2 D. Maxflow
Difficulty:None
問題
$ H行$ W列のグリッドがある。障害物があるマスと無いマスがある。
$ 1×2のサイズもしくは$ 2×1のサイズのタイルをできるだけ多く敷き詰めたい。敷き詰められるタイルの数の最大値を求め、実際に構築せよ。
解法
マス目を$ (i+j)\%2の値で白と黒に塗り分けると二部マッチングに帰着される。 頂点を$ H*W+2個用意する。
$ A_{i,j}(0 \le i<H,0\le j<W)：マス$ (i,j)に対応する。
$ S：フローの始点。
$ T：フローの終点。
以下のような条件で辺を張る。
マス$ (i,j)に障害物がない場合
$ (i+j)\%2=0のとき、$ Sから$ A_{i,j}に容量1の辺を張る。
$ (i+j)\%2=1のとき、$ A_{i,j}から$ Tに容量1の辺を張る。
$ (i+j)\%2=0のとき、上下左右のマスに対応する頂点に向かって容量1の辺を張る。これがタイルを置くことに対応している。
タイルの数の最大値は$ Sから$ Tまでの最大フローである。
また、構築の際は、上下左右に向かって張られた辺のうち流量が1であるものが1つのタイルに対応しているのでそれをもとに復元すればよい。
実装
code:cpp
using namespace std;
using namespace atcoder;
int dx8 = {0,1,0,-1,-1,-1,1,1},dy8={1,0,-1,0,-1,1,-1,1}; int main(){
int n,m;
cin >> n >> m;
vector<string>s(n);
for(auto&i:s)cin >> i;
mf_graph<int>g(n*m+2);
int S = n*m,T = n*m+1;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
int idx = i*m+j;
if((i+j)%2==0)g.add_edge(S,idx,1);
else g.add_edge(idx,T,1);
}
if((i+j)%2==0)for(int k = 0;k<4;k++){
unsigned int ni = i + dxk,nj = j + dyk; if(ni<n and nj<m){
int nidx = ni*m+nj;
g.add_edge(idx,nidx,1);
}
}
}
}
cout << g.flow(S,T) << endl;
for(auto i :g.edges()){
if(i.flow==1){
if(i.from==S or i.to==T)continue;
int si = i.from/m,sj = i.from%m;
int ti = i.to/m,tj = i.to%m;
if(si==ti){
//横！
auto v = minmax(sj,tj);
}
else if(sj==tj){
//縦！
auto v = minmax(si,ti);
}
}
}
for(auto i:s)cout<<i<<"\n";
cout<<endl;
}